The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the inventors hereof, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
This disclosure relates generally to data decoding, and more particularly to a unified architecture for processing LDPC codes with different circulant sizes using a common decoding architecture.
LDPC codes have become an important component of some error correcting systems. LDPC codes may employ many different types of parity check matrices. For example, the structure of an LDPC code's parity check matrix may be random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as quasi-cyclic low density parity check (QC-LDPC) codes.
As used herein, the term “message” refers to a numerical value, usually representing a log likelihood ratio (LLR). An LDPC decoder may decode LDPC codes using an iterative message-passing algorithm, such as a min-sum decoding algorithm. Iterative algorithms of this type may decode a received codeword using an iterative process in which each iteration includes two update steps involving check nodes and variable nodes.
An LDPC decoder may further use a layered approach to decode LDPC codes, which is sometimes referred to as layered decoding. Layered decoding exploits the fact that a QC-LDPC code's parity check matrix consists of circular submatrices or so-called “circulants.” The size of these circulants corresponds to the number of check node processors necessary to implement layered decoding and determines to what extent the processing of the parity check matrix can be parallelized. For example, a parity check matrix composed of circulants of size Sc can be implemented using Sc check node processors.
Within an LDPC decoder, the layered decoding approach for a QC-LDPC codeword may require a circular shifter to be used. The circular shifter may be responsible for shifting Sc LLR messages, each from a different check node processor, in one layer of processing. The amount of shift to be applied by the circular shifter may be determined based on the maximum shift necessary for a message. At greatest, the maximum shift may be equal to Sc, the size of the circulants in the quasi-cyclic parity check matrix associated with the QC-LDPC code. In this case, a circular shifter that accepts Sc inputs and provides Sc outputs may be used to appropriately shift the LLR messages. This Sc×Sc circular shifter may be implemented using a barrel shifter that hierarchically shifts the input sequence of each of the LLR messages in ┌log2 Sc┐ steps. The complexity of this circular shifter may therefore be proportional to ┌log2 Sc┐.
The amount that the LLR messages must be shifted may be determined by the difference in shifts between the first non-zero circulant in the column associated with the grouped variable nodes to which the LLR messages are sent and the previous non-zero circulant in the same column of the quasi-cyclic parity check matrix in the mother matrix representation. LLR messages may be sent from, for example, a channel detector to a layered LDPC decoder in segments smaller than the circulant size Sc. LLR messages may be sent in this manner because of bandwidth constraints in the channel between a channel detector and a layered LDPC decoder. Subsequent shifting of LLR messages may be done by the circular shifter used in layered decoding.
In some scenarios, a user device may need to be able to process different types of LDPC codes, such as LDPC codes with different circulant sizes. For example, in some applications, different degrees of error protection may be desirable depending for different types of information that are being exchanged between a transmitter and a reference (e.g., control information versus user data). One way of achieving different degrees of error protection is to use LDPC codes with different parameters, such as LDPC codes with different circulant sizes. However, supporting the decoding of more than one LDPC code in a user equipment device comes at the expense of implementation complexity. In some implementations, this may require separate decoding hardware that is dedicated to each of the multiple LDPC codes.
In view of the above, there exists a need for reducing the complexity of decoder implementations that support the decoding of multiple LDPC codes. Such techniques have the benefit of increased computational efficiency, decreased routing congestion, and may lead to improved application performance.